package code2101_2200.code80_90;

import java.util.Stack;

/**
 * 输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)
 *
 * B是A的子结构， 即 A中有出现和B相同的结构和节点值。
 *
 * 例如:
 * 给定的树 A:
 *
 *      3
 *     / \
 *    4   5
 *   / \
 *  1   2
 *
 *  给定的树 B：
 *     4
 *   /
 * 1
 * 返回 true，因为 B 与 A 的一个子树拥有相同的结构和节点值。
 *
 * 输入：A = [1,2,3], B = [3,1]
 * 输出：false
 *
 * 输入：A = [3,4,5,1,2], B = [4,1]
 * 输出：true
 */
public class _2183isSubStructure {

    /**
     * 思考 ： 类似于深度优先遍历。
     * 双层循环，第一层循环找子结构的初始点，第二层循环看结构是否一致
     *
     * 暴力解决！
     * 执行用时：     * 5 ms     * , 在所有 Java 提交中击败了     * 5.96%     * 的用户
     * 内存消耗：     * 40.8 MB     * , 在所有 Java 提交中击败了     * 5.14%     * 的用户
     *
     * 这必须得看题解了！！！！
     * @param A
     * @param B
     * @return
     */
    public boolean isSubStructure0(TreeNode A, TreeNode B) {
        if(A!=null&&B==null)return false;
        if(A==null&&B!=null)return false;
        Stack<TreeNode> stack1 = new Stack<>();
        stack1.push(A);
        Stack<TreeNode> stack2;
        TreeNode node;
        while (!stack1.isEmpty()){
            node = stack1.pop();
            // 如果此节点和B节点初始节点类似
            if(node.val == B.val){
                TreeNode aRoot = node;
                TreeNode bCopy = B;
                TreeNode nodeA = new TreeNode();
                TreeNode nodeB = new TreeNode();
                stack2 = new Stack<>();
                stack2.push(bCopy);
                stack2.push(aRoot);
                while (stack2.size()>1){
                    nodeA = stack2.pop();
                    nodeB = stack2.pop();
                    if(nodeA.val!=nodeB.val)break;
                    if(nodeA.left==null&&nodeA.right==null&&nodeB.left==null&&nodeB.right==null)continue;
                    if(nodeB.left!=null){
                        stack2.push(nodeB.left);
                        if(nodeA.left!=null){
                            stack2.push(nodeA.left);
                        }else {
                            break;
                        }
                    }
                    if(nodeB.right!=null){
                        stack2.push(nodeB.right);
                        if(nodeA.right!=null){
                            stack2.push(nodeA.right);
                        }else {
                            break;
                        }
                    }
                }
                if(stack2.isEmpty()&&(nodeA.val==nodeB.val)){
                    return true;
                }
            }
            if(node.left!=null)stack1.push(node.left);
            if(node.right!=null)stack1.push(node.right);
        }
        return false;
    }

    /**
     * 估计最简单的方式就是递归
     *
     * 执行用时：     * 0 ms     * , 在所有 Java 提交中击败了     * 100.00%     * 的用户
     * 内存消耗：     * 40.2 MB     * , 在所有 Java 提交中击败了     * 70.52%     * 的用户
     * @param A
     * @param B
     * @return
     */
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        return (A != null && B != null) && (recur(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B));
    }
    boolean recur(TreeNode A, TreeNode B) {
        if(B == null) return true;
        if(A == null || A.val != B.val) return false;
        return recur(A.left, B.left) && recur(A.right, B.right);
    }

}
